package leetcode.hot100;

/**
 * leetcode-hot100: 相交链表
 * 测试链接: https://leetcode.cn/problems/intersection-of-two-linked-lists/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * 给你两个单链表的头节点headA和headB，请找出并返回两个单链表相交的起始节点，
 * 如果两个链表不存在相交节点，返回null
 */

class ListNode{
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class IntersectionOfTwoLinkedLists {

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //统计链表长度
        int lenA = 0, lenB = 0;
        ListNode cur = headA;
        while(cur != null){
            cur = cur.next;
            lenA++;
        }
        cur = headB;
        while(cur != null){
            cur = cur.next;
            lenB++;
        }
        //长度差只可能是相交前的部分差的，因为是单链表，相交后的节点是共用的
        int step = lenA - lenB;
        for(int i = 0; i < Math.abs(step); i++){
            //让长的链表先走一个长度差，这样他们到相交点的距离就一致了
            if(step < 0){
                headB = headB.next;
            }else{
                headA = headA.next;
            }
        }
        while(headA != null && headB != null){
            if(headA == headB){
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}
